翻訳と辞書 Words near each other ・ K-X-P ・ K-Y Jelly ・ K-Z ・ K. (novel) ・ K-frame ・ K-function ・ K-Gee ・ K-graph C*-algebra ・ K-group ・ K-Hill (artist) ・ K-Hito ・ K-Hits ・ K-hole ・ K-homology ・ K-ID ・ K-independent hashing ・ K-index ・ K-index (meteorology) ・ K-Jee ・ K-K-K-Katy ・ K-Klass ・ K-LEE Radio ・ K-Liber ・ K-Line ・ K-line ・ K-line (artificial intelligence) ・ K-line (spectrometry) ・ K-Lite Codec Pack ・ K-Lo ・ K-Love Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク K-independent hashing ： ウィキペディア英語版 K-independent hashing A family of hash functions is said to be $k$-independent or $k$-universal〔 〕 if selecting a hash function at random from the family guarantees that the hash codes of any designated $k$ keys are independent random variables (see precise mathematical definitions below). Such families allow good average case performance in randomized algorithms or data structures, even if the input data is chosen by an adversary. The trade-offs between the degree of independence and the efficiency of evaluating the hash function are well studied, and many $k$-independent families have been proposed. == Introduction == The goal of hashing is usually to map keys from some large domain (universe) $U$ into a smaller range, such as $m$ bins (labelled $()\; =\; \backslash$). In the analysis of randomized algorithms and data structures, it is often desirable for the hash codes of various keys to "behave randomly". For instance, if the hash code of each key were an independent random choice in $()$, the number of keys per bin could be analyzed using the Chernoff bound. A deterministic hash function cannot offer any such guarantee in an adversarial setting, as the adversary may choose the keys to be the precisely the preimage of a bin. Furthermore, a deterministic hash function does not allow for ''rehashing'': sometimes the input data turns out to be bad for the hash function (e.g. there are too many collisions), so one would like to change the hash function. The solution to these problems is to pick a function ''randomly'' from a large family of hash functions. The randomness in choosing the hash function can be used to guarantee some desired random behavior of the hash codes of any keys of interest. The first definition along these lines was universal hashing, which guarantees a low collision probability for any two designated keys. The concept of $k$-independent hashing, introduced by Wegman and Carter in 1981,〔 〕 strengthens the guarantees of random behavior to families of $k$ designated keys, and adds a guarantee on the uniform distribution of hash codes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K-independent hashing」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.